package lib;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Random;

/**
 * 
 * @author  Igor Covganet
 * @Created Jul 21, 2010
 * 
 * The methods in this class are tested and work well.
 */
public class MaxFlow {
	int[][] flow = null;
	int[][] cFlow = null;
	LinkedList<Integer> cPath = new LinkedList<Integer>();
	int bestRes = 0;
	
	boolean[] used = null;
	/** given graph with entry point 0, and exit point (length - 1), with possible flow matrix int[][] flow, return the max flow. */
	public int getMaxFlow(int[][] flow) {
		this.flow = flow;
		// the current flow
		cFlow = new int[flow.length][flow.length];
		// find augmenting paths and adjust the result
		used = new boolean[flow.length];
		while(dfs(0, Integer.MAX_VALUE) > 0);
		
		return bestRes;
	}
	
	// should find the augmenting path and fill the flow, returning the additional value
	private int dfs(int node, int maxFlow) {
		if(node == flow.length - 1) {
			int prev = 0;
			for(int val : cPath) {
				if(val == prev) {
					continue;
				}
				cFlow[prev][val] += maxFlow;
				prev = val;
			}
			cFlow[prev][node] += maxFlow;
			bestRes += maxFlow;
			Arrays.fill(used, false);
			
			return maxFlow;
		}
		
		cPath.add(node);
		used[node] = true;
		for(int i = 0; i < flow.length; i++) {
			if(i == node || used[i]) {
				continue;
			}
			if(flow[node][i] > cFlow[node][i]) {
				int res = dfs(i, Math.min(maxFlow, flow[node][i] - cFlow[node][i]));
				if(res > 0) {
					cPath.removeLast();
					return res;
				}
			}
		}
		
		cPath.removeLast();
		return 0;
	}
}
